package 代码记录.剑指offer错题本;

/**
 * @author zx
 * @create 2022-06-02 21:35
 */
public class 二叉搜索树的后序遍历序列_33 {
    /**
     * 二叉搜索树的性质，二叉搜索树是一个有序树：
     * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
     * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
     * 它的左、右子树也分别为二叉搜索树
     * 采用递归分治思想通过递归判断所有子树的正确性，所有子树都满足二叉搜索树的性质则说明
     * 此后序遍历数组是二叉搜索树后序遍历得到的。
     * @return
     * 中间处理逻辑
     * 寻找第一个大于根节点的节点,索引记为midIndex.此时,可划分出二叉搜索树的左子树区间[start, midIndex - 1]
     * 右子树区间 [midIndex, end - 1]
     * 看题解下的那个图解
     */
    public boolean verifyPostorder(int[] postorder) {
        return traversal(postorder, 0, postorder.length - 1);
    }
    private boolean traversal(int[] postorder, int start, int end) {
        //递归终止条件
        if(start >= end) {
            return true;
        }
        int i = start;
        //中间处理逻辑(划分左子区间)
        while(postorder[i] < postorder[end]) {
            i++;
        }
        //记录分割点(划分右子区间)
        int midIndex = i;
        while(postorder[i] > postorder[end]) {
            i++;
        }
        //递归左右子树
        return i == end && traversal(postorder, start, midIndex - 1) &&
                traversal(postorder, midIndex, end-1);
    }
}
